import java.util.ArrayList;
import java.util.List;

public class Solution1 {
    public int aim;
    public List<Integer> path;
    public List<List<Integer>> ret;

    public List<List<Integer>> combinationSum(int[] nums, int target) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        aim = target;

        dfs(nums, 0, 0);
        return ret;
    }

    //解法二
    public void dfs1(int[] nums, int pos ,int sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }

        if(sum > aim || pos == nums.length) {
            return;
        }

        for(int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i, sum + nums[i]);
            path.remove(path.size() - 1);// 恢复现场
        }
    }

    // 解法二
    public void dfs(int[] nums, int pos ,int sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }

        if(sum > aim || pos == nums.length) {
            return;
        }

        // 枚举 nums[pos] 使用多少个
        for(int k = 0; k * nums[pos] + sum <= aim; k++) {
            if(k != 0) {
                path.add(nums[pos]);

            }
            dfs(nums, pos + 1, sum + k * nums[pos]);
        }

        // 恢复现场
        for(int k = 1; k * nums[pos] + sum <= aim; k++) {
            path.remove(path.size() - 1);
        }
    }
}
